﻿/*
 * sparce_map.hpp
 *
 *  Created on: 2020年2月23日
 *      Author: Dylan.Gao
 */

#ifndef _DM_SPARCE_MAP_HPP_
#define _DM_SPARCE_MAP_HPP_

#include <dm/link_next_simple.hpp>

namespace dm{

/**
 * 稀疏映射
 * 用于实现着色索引等功能
 */
template<typename TKey,typename TValue>
class TCSparceMap{
public:
	struct STagValue{
		TKey k;
		TValue v;
	};

	typedef TCLinkNextSimple<STagValue*> list_t;
public:
	TCSparceMap():m_l(NULL){};
	~TCSparceMap(){ if( m_l ) delete m_l;};

	const STagValue* find( const TKey& k )const{
		const list_t* l = findOrPre(k,m_l);
		if( l && l->get()->k==k )
			return l->get();
		return NULL;
	}

	STagValue* find( const TKey& k ){
		list_t* l = findOrPre(k,m_l);
		if( l && l->get()->k==k )
			return l->get();
		return NULL;
	}

	bool add( const TKey& k,const TValue& v ){
		list_t* l = findOrPre(k,m_l);
		if( l ){
			if( l->get()->k==k )
				return false;	// 已经存在

			STagValue* tv = new STagValue;
			tv->k = k;
			tv->v = v;
			l->insert(tv);
			return true;
		}else{
			STagValue* tv = new STagValue;
			tv->k = k;
			tv->v = v;

			if( m_l )
				m_l = l->pushHead(tv);
			else
				m_l = new list_t(tv);

			return true;
		}
	}

	bool set( const TKey& k,const TValue& v ){
		list_t* l = findOrPre(k,m_l);
		if( l && l->get()->k==k ){
			l->get()->v = v;
			return true;
		}

		return false;
	}

	void addOrSet( const TKey& k,const TValue& v ){
		list_t* l = findOrPre(k,m_l);
		if( l ){
			if( l->get()->k==k )
				l->get()->v = v;
			else{
				STagValue* tv = new STagValue;
				tv->k = k;
				tv->v = v;
				l->insert(tv);
			}
		}else{
			STagValue* tv = new STagValue;
			tv->k = k;
			tv->v = v;
			if( m_l )
				m_l = l->pushHead(tv);
			else
				m_l = new list_t(tv);
		}
	}

	inline unsigned int size()const{
		return m_l?m_l->size():0;
	}

	const STagValue* getByIndex( const unsigned int& idx )const{
		if( m_l==NULL )
			return NULL;

		const list_t* l = m_l;

		for( unsigned int i=0;i<idx;++i ){
			if( l->next() )
				l = l->next();
			else
				return NULL;
		}

		return l->get();
	}

	inline void clear(){
		if( m_l ){
			delete m_l;
			m_l = NULL;
		}
	}

private:
	/**
	 * 查找存在的记录或者之前的记录
	 * @param k
	 * @param l
	 * @return
	 */
	list_t* findOrPre( const TKey& k,list_t* l )const{
		if( l==NULL || l->get()->k > k  )
			return NULL;

		while( l ){
			if( l->get()->k>k )
				return NULL;
			if( l->get()->k==k ||l->next()==NULL || l->next()->get()->k>k )
				return l;

			l = l->next();
		}
		return NULL;
	}

	const list_t* findOrPre( const TKey& k,const list_t* l )const{
		if( l==NULL || l->get()->k > k  )
			return NULL;

		while( l ){
			if( l->get()->k>k )
				return NULL;
			if( l->get()->k==k ||l->next()==NULL || l->next()->get()->k>k )
				return l;

			l = l->m_next;
		}
		return NULL;
	}

private:
	list_t* m_l;
};

}

#endif /* INCLUDE_DM_SPARCE_MAP_HPP_ */
